package course.p3_arraysSort.exa03_shellSort;

import java.util.Arrays;

public class ShellSort {


    /**
     * 希尔排序核心实现（C语言版数据结构168）
     * @param array 排序数组
     * @param n 初始间距*2
     */
    public static <T extends Comparable<T>> T[] sort(T[] array,int n) {
        int i,j,increment;
        T tem;
        for(increment = n/2; increment>0; increment /= 2){
            for(i = increment; i<n; i++){
                tem = array[i];
                for(j = i;j >= increment;j -= increment){
                    if(tem.compareTo(array[j-increment])<0)
                        array[j] = array[j-increment];
                    else break;
                }
                array[j] = tem;
            }
        }
        return array;
    }

    /**
     * 希尔排序基础实现
     * @param array 目标数组
     * @param n 初始间距
     */
    public static void shellSort(int[] array, int n) {
        for(int sub = n; sub>0 ; sub /= 2){
            for(int i= sub; i<array.length; i++) {
                int tem = array[i];
                int j;
                // 这里加入了插入排序的思想
                for( j = i; j >= sub&&tem<array[j-sub]; j -= sub) {
                    array[j] = array[j-sub];
                }
                array[j] = tem;
            }
        }
    }

    /**
     * 希尔排序核心实现
     * @param array 排序数组
     * @param n 数组长度
     */
    public static <T extends Comparable<T>> T[] sort2(T[] array,int n) {
        //计算初始间隔
        int increment = n/2;
        for(int i=increment;i>0;i--){
            int index = 0;
            while (index<n){
                int bigIndex = index+i;
                if(bigIndex>n-1){
                    bigIndex = n-1;
                }
                if(array[index].compareTo(array[bigIndex])>0){
                    T temp = array[index];
                    array[index] = array[bigIndex];
                    array[bigIndex] = temp;
                }
                index+=i;
            }
        }
        return array;
    }


    public static void shellSortTest(){
        int[] numbs = {3,9,2,5,7,1};
        shellSort(numbs,numbs.length/2);
        System.out.println(Arrays.toString(numbs));
    }

    public static void main(String[] args) {
        shellSortTest();
    }


}
